package com.leetcode.partition3;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/18 8:44
 */
public class LC257二叉树的所有路径 {

    public static List<String> binaryTreePaths(TreeNode root) {
//        List<String> answer = new ArrayList<>();
//        backtracking(root, answer, "");
//        return answer;
        return iteration(root);
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1, new TreeNode(2, null, new TreeNode(5)), new TreeNode(3));
        System.out.println(binaryTreePaths(n1));
    }

    private static List<String> iteration(TreeNode root) {
        List<String> answer = new ArrayList<>();
        Stack<TreeNode> treeNodeStack = new Stack<>();
        Stack<String> pathStack = new Stack<>();
        treeNodeStack.push(root);
        pathStack.add(String.valueOf(root.val));
        while (!treeNodeStack.isEmpty()) {
            TreeNode cur = treeNodeStack.pop();
            String path = pathStack.pop();
            if (cur.left == null && cur.right == null) answer.add(path);
            if (cur.right != null) {
                treeNodeStack.push(cur.right);
                pathStack.push(path + "->" + cur.right.val);
            }
            if (cur.left != null) {
                treeNodeStack.push(cur.left);
                pathStack.push(path + "->" + cur.left.val);
            }
        }
        return answer;
    }
    
    private static void backtracking(TreeNode root, List<String> answer, String path) {
        path += root.val;
        if (root.left == null && root.right == null) {
            answer.add(path);
            return;
        }
        if (root.left != null) backtracking(root.left, answer, path + "->");
        if (root.right != null) backtracking(root.right, answer, path + "->");
    }
}
